import java.util.*;

public class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return new int[0];
        }
        int[] res = new int[matrix.length * matrix[0].length];
        int index = 0;
        int start = 0;
        while (start * 2 < matrix.length && start * 2 < matrix[0].length) {
            index = lap(matrix, start, res, index);
            ++start;
        }
        return res;
    }

    private int lap(int[][] matrix, int start, int[] res, int index) {
        int height = matrix.length - 2 * start;
        int width = matrix[start].length - 2 * start;
        for (int i = 0; i < width; i++) {
            res[index++] = matrix[start][start + i];
        }
        if (height >= 2) {
            for (int i = 1; i < height; i++) {
                res[index++] = matrix[start + i][start + width - 1];
            }
        }
        if (height >= 2 && width >= 2) {
            for (int i = width - 2; i >= 0; i--) {
                res[index++] = matrix[start + height - 1][start + i];
            }
        }
        if (width >= 2 && height >= 3) {
            for (int i = height - 2; i > 0; i--) {
                res[index++] = matrix[start + i][start];
            }
        }
        return index;
    }

    public static void main(String[] args) {
        /*int[][] matrix = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
        };*/
        /*int[][] matrix = {
                {6, 7, 9},
        };*/
        int[][] matrix = {
                {1, 2},
                {3, 4},
        };
        System.out.println(Arrays.toString(new Solution().spiralOrder(matrix)));
    }
}
